//
// Created by Semir on 2020/5/15.
//

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    explicit TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void ConnectTreeNode(TreeNode* pRoot, TreeNode* pLeft, TreeNode* pRight) {
    if (pRoot == nullptr) {
        return;
    }
    pRoot->left = pLeft;
    pRoot->right = pRight;
}

TreeNode* BuildTree1() {
    auto* node1 = new TreeNode(8);
    auto* node2 = new TreeNode(6);
    auto* node3 = new TreeNode(10);
    auto* node4 = new TreeNode(13);
    auto* node5 = new TreeNode(5);
    auto* node6 = new TreeNode(9);
    auto* node7 = new TreeNode(7);

    auto* node8 = new TreeNode(2);
    auto* node9 = new TreeNode(4);
    auto* node10 = new TreeNode(3);
    auto* node11 = new TreeNode(8);
    auto* node12 = new TreeNode(6);
    auto* node13 = new TreeNode(1);
    auto* node14 = new TreeNode(5);
    auto* node15 = new TreeNode(8);

    ConnectTreeNode(node1, node2, node3);
    ConnectTreeNode(node2, node4, node5);
    ConnectTreeNode(node3, node6, node7);
    ConnectTreeNode(node4, node8, node9);
    ConnectTreeNode(node5, node10, node11);
    ConnectTreeNode(node6, node12, node13);
    ConnectTreeNode(node7, node14, node15);

    return node1;
}

void InsertToRes(vector<vector<int>>& res, deque<TreeNode*>& Q, bool leftToRight) {
    vector<int> newVec;
    if (leftToRight) {
        for (auto & iter : Q) {
            newVec.emplace_back(iter->val);
        }
    } else {
        for (auto iter = Q.rbegin(); iter != Q.rend(); iter++) {
            newVec.emplace_back((*iter)->val);
        }
    }
    res.emplace_back(newVec);
}

vector<vector<int> > Print(TreeNode* pRoot) {
    vector<vector<int>> res;
    if (pRoot == nullptr) {
        return res;
    }
    deque<TreeNode*> Q;
    auto* mkNode = new TreeNode(0);
    TreeNode* pNode = pRoot;
    bool leftToRight = true;
    Q.push_back(mkNode);
    Q.push_back(pNode);
    while (!Q.empty()) {
        pNode = Q.front();
        Q.pop_front();
        if (pNode != mkNode) {
            if (pNode->left) {
                Q.push_back(pNode->left);
            }
            if (pNode->right) {
                Q.push_back(pNode->right);
            }
        } else {
            if (Q.empty()) {
                break;
            }
            InsertToRes(res, Q, leftToRight);
            leftToRight = !leftToRight;
            Q.push_back(mkNode);
        }
    }
    return res;
}

int main() {
    TreeNode* pRoot = BuildTree1();
    vector<vector<int>> res = Print(pRoot);
    cout << res.size() << endl;
    return 0;
}